package main

// 215. 数组中的第K个最大元素
func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	k := 2
	//nums := []int{3, 2, 3, 1, 2, 4, 5, 5, 6}
	//k := 4
	largest := findKthLargest(nums, k)
	println(largest)
}

func findKthLargest(nums []int, k int) int { // 快速排序，中位为k时返回，当前中位值小于k时处理右侧，当前中位大于k时处理左侧
	n := len(nums)
	return quickSelect(nums, 0, n-1, n-k)
}

func quickSelect(nums []int, l, r, k int) int {
	if l == r {
		return nums[k]
	}
	partition := nums[l]
	i := l - 1
	j := r + 1
	for i < j {
		for i++; nums[i] < partition; i++ {
		}
		for j--; nums[j] > partition; j-- {
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if k <= j {
		return quickSelect(nums, l, j, k)
	} else {
		return quickSelect(nums, j+1, r, k)
	}
}

// CountSort1 计数排序
func CountSort1(array []int) []int { // 有复数，不能处理
	arrLen := len(array)
	if arrLen < 2 {
		return array
	}

	maxNum := array[0]
	for _, arr := range array {
		if arr > maxNum {
			maxNum = arr
		}
	}

	countArray := make([]int, maxNum+1)
	for _, item := range array {
		countArray[item]++
	}

	var resArray []int
	for idx, item := range countArray {
		for i := 0; i < item; i++ {
			resArray = append(resArray, idx)
		}
	}

	return resArray
}

func fastKSort(nums []int, low, high int, k int) {
	if low < high {
		half := partition5(nums, low, high)
		//如果这个half, 位置等于倒数第K个，就可以返回了
		if half == len(nums)-k {
			return
		} else if half > (len(nums) - k) {
			fastKSort(nums, low, half-1, k)
		} else {
			fastKSort(nums, half+1, high, k)
		}
	}
}

func partition5(nums []int, low, high int) (half int) {
	halfNum := nums[high]
	i := low - 1
	for j := low; j < high; j++ {
		if nums[j] < halfNum {
			i++
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	nums[i+1], nums[high] = nums[high], nums[i+1]
	return i + 1
}

// 215. 数组中的第K个最大元素
//中等
//相关标签
//相关企业
//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//示例 1:
//
//输入: [3,2,1,5,6,4], k = 2
//输出: 5
//示例 2:
//
//输入: [3,2,3,1,2,4,5,5,6], k = 4
//输出: 4
//
//提示：
//
//1 <= k <= nums.length <= 105
//-104 <= nums[i] <= 104
